Dijkstra 路径规划算法原理详解及 Python 代码实现

2023-03-11 04:25| 来源: 网络整理| 查看: 265

荷兰数学家 E.W.Dijkstra 于 1959 年提出了 Dijkstra 算法，它是一种适用于非负权值网络的单源最短路径算法，同时也是目前求解最短路径问题的理论上最完备、应用最广的经典算法。它可以给出从指定节点到图中其他节点的最短路径，以及任意两点的最短路径。

Dijkstra 算法是一种基于贪心策略的最短路径算法，该种算法的原理是按照路径长度逐点增长的方法构造一棵路径树，从而得出从该树的根节点（即指定节点）到其他所有节点的最短路径。

Dijkstra 算法的核心思想是：设置两个点的集合 S 和 T。集合 S 中存放已找到最短路径的节点，集合 T 中存放当前还未找到最短路径的节点。

具体实现过程如下图所示：

下面将用一个示例来讲述算法的原理过程。

如图所示，一个有向权值图，利用 Dijkstra算法找到从节点1 到节点 6 的最短路径。

首先进行初始化，初始化一个空的 open list、close list 以及 parent。将起点及其距离信息放入到 open list 中，将起点及其父亲节点放入 parent 中，由于其是起点，所以设置其父节点为 None。

open list 中存放那些已经访问的从该节点到起点有路径的结点（有路径但不一定是最优路径）。

close list 中存放那些已经找到最优路径的结点。

parent 存放结点的父子关系，方便后面路径回溯。

注意：其实 open list 中应该存放所有未找到最短路径的结点，存放时由于要设置其距起点的距离，初始化时通常设置为+Inf.后面逐个访问结点时到再更新其相应的距离值。其实和现在的做法是一样的，将 open list 初始化为空，逐个访问到结点时再往里添加或者更新。两者皆可。

幻灯片2

按步骤执行。

close list 中新加入的结点为 1(0), 遍历其邻接结点 2 、4，两结点均未在 close list 中，所以计算其距离（即到起点的距离）如下图所示，并将其添加如 open list 中。将结点 2 、4的继承关系即 {2: 1，4: 1}添加进 parent 中。从 open list 中找到距离最小的结点，即 4(1),并添加到 close list 中。

幻灯片3

按步骤执行。

close list 中新加入的结点为 4(1), 遍历其邻接结点 3、 6、 7、 5，四个结点均未在 close list 中，所以计算其距离（即到起点的距离），如下图所示。并将其添加如 open list 中。将结点 3、 6、 7、 5的继承关系即 {3: 4, 6: 4, 7: 4，5: 4}添加进 parent 中。从 open list 中找到距离最小的结点，即 2(2),并添加到 close list 中。

幻灯片4

按步骤执行。

close list 中新加入的结点为 2(2), 遍历其邻接结点 4、 5，由于结点 4 已经在 close list 中，所以只需计算结点5的距离，如下图所示，由于计算的新的距离为13，大于open list 中结点 5 原来的距离 3，所以不进行更新。同时也不更新 parent 中结点 5 的继承关系从 open list 中找到距离最小的结点，此时有两个距离最小的结点，3(3) 和 5(3), 任选其一即可，在此选 3(3), 并添加到 close list 中。

幻灯片5

按步骤执行。

close list 中新加入的结点为 3(3), 遍历其邻接结点 1、 6，由于结点 1 已经在 close list，所以不用考虑，只需计算结点 6 的距离，如下图所示，计算后得到的距离为 8，小于 open list 中结点6 原来的距离 9，所以更新 open list 中结点 6 的距离为 8. 同时更新 parent 中结点 6 的继承关系为 {6： 3}从 open list 中找到距离最小的结点，即 5(3),并添加到 close list 中。

幻灯片6

按步骤执行。

close list 中新加入的结点为 5(3), 遍历其邻接结点 7，结点 7 未在close list 中，计算其距离，如下图所示，计算后的距离为 9，大于 open list 中结点 7 的距离 5，所以不进行更新。同时也不更新 parent 中结点 7 的继承关系。从 open list 中找到距离最小的结点，即 7(5),并添加到 close list 中。

幻灯片7

按步骤执行。

close list 中新加入的结点为 7(5), 遍历其邻接结点 6. 结点 6 未在 close list 中，所以计算其距离，如下图所示。计算后的距离为 6，小于 open list 中结点 6 的距离 8，所以将 open list 中结点 6 的距离更新为 6.同时更新 parent 中结点 6 的继承关系为 {6:7}从 open list 中找到距离最小的结点，即 6(6),并添加到 close list 中。至此，找到终点。

幻灯片8

路径回溯。

根据 parent 中的继承关系，从终点向起点回溯，得到从起点 1 到终点 6 的最短路径为：1 => 4 => 7 => 6, 最短路径长为：6.

总结上述流程，可以得到以下算法代码框架：

代码框架, style="zoom: 50%;"

Python 代码实现 class Dijkstra: def __init__(self, graph, start, goal): self.graph = graph # 邻接表 self.start = start # 起点 self.goal = goal # 终点 self.open_list = {} # open 表 self.closed_list = {} # closed 表 self.open_list[start] = 0.0 # 将起点放入 open_list 中 self.parent = {start: None} # 存储节点的父子关系。键为子节点，值为父节点。方便做最后路径的回溯 self.min_dis = None # 最短路径的长度 def shortest_path(self): while True: if self.open_list is None: print('搜索失败，结束！') break distance, min_node = min(zip(self.open_list.values(), self.open_list.keys())) # 取出距离最小的节点 self.open_list.pop(min_node) # 将其从 open_list 中去除 self.closed_list[min_node] = distance # 将节点加入 closed_list 中 if min_node == self.goal: # 如果节点为终点 self.min_dis = distance shortest_path = [self.goal] # 记录从终点回溯的路径 father_node = self.parent[self.goal] while father_node != self.start: shortest_path.append(father_node) father_node = self.parent[father_node] shortest_path.append(self.start) print(shortest_path[::-1]) # 逆序 print('最短路径的长度为：{}'.format(self.min_dis)) print('找到最短路径，结束！') return shortest_path[::-1], self.min_dis # 返回最短路径和最短路径长度 for node in self.graph[min_node].keys(): # 遍历当前节点的邻接节点 if node not in self.closed_list.keys(): # 邻接节点不在 closed_list 中 if node in self.open_list.keys(): # 如果节点在 open_list 中 if self.graph[min_node][node] + distance '2': 2, '4': 1}, '2': {'4': 3, '5': 11}, '3': {'1': 4, '6': 5}, '4': {'3': 2, '6': 8, '7': 4, '5': 2}, '5': {'7': 6}, '7': {'6': 1} } start = '1' goal = '6' dijk = Dijkstra(g, start, goal) dijk.shortest_path()

运行结果：

如果对您有帮助，记得在下面点赞呦！如果有问题也欢迎在下面评论区留言。

【本文地址】

公司简介

联系我们